package 所有的题类.ZF.分治算法;

public class 戳气球 {
    public static void main(String[] args) {
        int nums[]={3,1,5,8};
        System.out.println(maxCoins(nums));
    }
    public static int maxCoins(int[] nums) {
        return divideAndMerge(nums,0,nums.length-1,-1);
    }
    public static int divideAndMerge(int[]nums,int start,int end,int min){
        if(start==end){
            return nums[start];
        }
        int mid=(start+end)/2;
        int left=divideAndMerge(nums,start,mid,min);
        int right=divideAndMerge(nums,mid+1,end,min);
        if((left+right+nums[mid])>min){
            min=left+right+nums[mid];
        }
        return min;
    }


}
